'''
Created on 19/05/2014

@author: dingliangl
'''



from cj_lib import *
from properties import *

import math
import fractions


curr_file_name = 'A-large-practice'
#curr_file_name = 'A-small-practice'
#curr_file_name = 'test'

# map(int, input_lines.pop(0).split(' '))

def input_dividing_func(input_lines):
    total_case = int(input_lines.pop(0))
    case_inputs = []
    for i in range(total_case):
        N, M = map(int, input_lines.pop(0).split(' '))
        oep = []
        for i in range(M):
            oep.append(map(int, input_lines.pop(0).split(' ')))
        case_inputs.append([N, M, oep])
    return case_inputs

def calc_fee(o, e, p, N):
    if o == e:
        return 0
    x = e-o
    return (N*x - x*(x-1)/2) * p

def calc_total_fee(oep, N):
    f = 0
    for s in oep:
        f += calc_fee(s[0], s[1], s[2], N)
    return f
    
def process_func(func_input):
    N, M, oep = func_input
    inout = dict()
    for s in oep:
        o,e,p = s
        if not inout.has_key(o):
            inout[o] = [0, 0]
        if not inout.has_key(e):
            inout[e] = [0, 0]
        inout[o][0] += p
        inout[e][1] += p
    #print inout
    
    removingk = []
    for k in sorted(inout.keys()):
        if inout[k][0] == inout[k][1]:
            removingk.append(k)
            continue
        x = min(inout[k][0], inout[k][1])
        inout[k][0] -= x
        inout[k][1] -= x
    for k in removingk:
        del inout[k]
        
    #print inout
    fakeoep = []
    inoutseq = []
    for k in sorted(inout.keys()):
        inoutseq.append([k, inout[k][0] - inout[k][1], 0, 0])
    #print inoutseq
    
    removingk = []
    for i in range(len(inoutseq)):
        if inoutseq[i][1] == 0:
            removingk.append(i)
    for i in removingk[::-1]:
        inoutseq.pop(i)
    curr = 0
    for io in inoutseq:
        curr += io[1]
        io[2] = curr
        io[3] = 0
    if len(inoutseq) > 0:
        minc = -1
        for i in range(len(inoutseq) - 2, -1, -1):
            if minc < 0 or minc > inoutseq[i][2]:
                minc = inoutseq[i][2]
            inoutseq[i][3] = minc
    
    #print inoutseq
    while inoutseq != []:
        #print inoutseq
        down = []
        for i in range(len(inoutseq))[::-1]:
            io = inoutseq[i]
            if io[1] < 0:
                down = io
                break
        #down = inoutseq[-1]
        up = []
        for io in inoutseq:
            if io[3] > 0 and io[1] > 0:
                up = io
                break
        p = min(-down[1], up[1], up[3])
        down[1] += p
        up[1] -= p
        fakeoep.append([up[0], down[0], p])
        #print inoutseq
        #print fakeoep[-1]
        
        removingk = []
        for i in range(len(inoutseq)):
            if inoutseq[i][1] == 0:
                removingk.append(i)
        for i in removingk[::-1]:
            inoutseq.pop(i)
        curr = 0
        for io in inoutseq:
            curr += io[1]
            io[2] = curr
            io[3] = 0
        if len(inoutseq) > 0:
            minc = -1
            for i in range(len(inoutseq)-1)[::-1]:
                if minc < 0 or minc > inoutseq[i][2]:
                    minc = inoutseq[i][2]
                inoutseq[i][3] = minc
        
    
    fo = calc_total_fee(oep, N)
    ff = calc_total_fee(fakeoep, N)
    return (fo-ff)%1000002013

run_proc(process_func, input_dividing_func, curr_working_folder, curr_file_name)








